package com.zhu.algorithm.sort;

import com.zhu.algorithm.sort.impl.Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/24/14:31
 * @Description:插入排序
 *
 * 算法步骤
 * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 *
 * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
 */
public class InsertionSort implements Sort {

    @Override
    public int[] sort(int[] sourceArray){

        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        long A=System.currentTimeMillis();

        for (int i=1; i<arr.length; i++){
            int temp = arr[i];

            int j = i;
            while (j>0 && temp<arr[j-1]){
                arr[j] = arr[j-1];
                j--;
            }
            if (j!=i)
                arr[j] = temp;
        }

        long B=System.currentTimeMillis();
        System.out.println("插入排序所耗时间： "+(B-A)+"ms");

        return arr;

    }
}
